Introductory Graph Theory by Gary Chartrand

Author:Gary Chartrand
Language: eng
Format: mobi
ISBN: 9780486134949
Publisher: Dover Publications
Published: 2012-07-17T21:00:00+00:00

7.1 A Traffic System Problem: An Introduction to Orientable Graphs

Suppose we wish to design a traffic system for a small college town in the East. Since the town is small and traffic is ordinarily light, a complex traffic system is not needed; so we agree to make all streets two-way. Certain minimum requirements are necessary; for example, we want to be able to reach any intersection from any other intersection. Also, the street crews make any necessary road repairs during the week. If a crew is repairing a street between two consecutive intersections, thereby blocking off the street, it would be convenient if a motorist could still reach any intersection while the repairs are in progress.

We can easily represent this situation by a graph G. The vertex set of G corresponds to the street intersections, and two vertices are joined by an edge if, in the corresponding two intersections, it is possible to travel from one to the other without passing through a third intersection. The fact that we can reach any intersection in the traffic system from any other intersection implies that G must be connected. If we want to travel between any two intersections even when a street between consecutive intersections is blocked off, then the graph G can have no bridges.

Let us now suppose that on football Saturdays, traffic becomes so heavy we need a different traffic pattern. We decide to convert all streets into one-way streets. Of course, we would like to make this change in such a way that afterwards, using one-way streets, it is still possible to travel (legally) from any intersection to any other intersection. This leads us to our problem.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.